//https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked
//补充：注释的代码，也是一种解法；

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

class Solution {
public:

    vector<vector<int>>res; //记录答案
    vector<int>path;   //记录路径

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //std::sort(candidates.begin(),candidates.end());
        dfs(candidates,0,target);
        return res;
    }

    void dfs(vector<int>&c,int u ,int target)
    {
        if(target < 0) return ;   //递归边界
        if(target == 0)
        {
            res.push_back(path);  //记录答案
            return ;
        }
        for(int i = u; i < c.size(); i++){
            if( c[i] <= target)  
            {
                path.push_back(c[i]);   //加入路径数组中
                dfs(c,i,target -  c[i]);// 因为可以重复使用，所以还是i
                path.pop_back();        //回溯，恢复现场
            }
            // else{
            //     return;
            // }
        }
    }
};